// https://leetcode.cn/problems/reverse-words-in-a-string/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 先整体反转字符串，颠倒单词顺序
// 2. 使用stringstream自动按空格分割单词
// 3. 对每个单词单独反转，恢复单词本身顺序
// 4. 拼接结果并去除末尾多余空格
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

class Solution 
{
public:
    string reverseWords(string s) 
    {
        reverse(s.begin(), s.end());
        stringstream ss(s);

        string res, word;
        while (ss >> word)
        {
            reverse(word.begin(), word.end());
            res += word;
            res += ' ';
        }
        res.pop_back();

        return res;
    }
};

int main()
{
    string s1 = "the sky is blue";
    string s2 = "  hello world  ";

    Solution sol;

    cout << sol.reverseWords(s1) << endl;
    cout << sol.reverseWords(s2) << endl;

    return 0;
}